#include <iostream>
#include <string>
#include <list>
#include <iomanip>

using namespace std;

/**
 *邻表法实现graph
 */
template<typename Object>
class graph_list
{  
private:
  class vertex;
  class edge
  {
  public:
    vertex *v;
    int weight;
    int direction;
    edge(){
      v = NULL;
      weight = 0;
      direction = -1;
    }
    
  };
  class vertex
  {
  public:
    string name;
    Object data;
    list<edge> edgeList;
  };
   
  list<vertex> vertexList;
  
  typename list<vertex>::iterator itr;
  typename list<edge>::iterator itrEdge;

public:
  void insertVertex( const Object &in_data,const string &in_name )
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
	
	if( (*itr).name == in_name )
	  return;
      }//防止顶点重名
    
    vertex temp;
    temp.name = in_name;
    temp.data = in_data;
    vertexList.insert( vertexList.end(),temp );
  }

  
  void deleteVertex( const string &name )
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	if( (*itr).name == name)
	  break;
      }
    
    if( (*itr).name != name )
          return;                        //在graph中没有找到要删除的顶点，返回.
    
    
    typename list<edge>::iterator itrEdge_tmp;
    
    
    for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)//删除所有边连接的顶点中的
      {
	 for( itrEdge_tmp = (*itrEdge).v->edgeList.begin(); itrEdge_tmp != (*itrEdge).v->edgeList.end(); itrEdge_tmp++)
	    {
	      
	      if( (*itrEdge_tmp).v->name == (*itr).name)
		{
		  (*itrEdge).v->edgeList.erase( itrEdge_tmp );
		  break;
		}
	    }
	 
      }
    
    (*itr).edgeList.clear();    
    vertexList.erase( itr );
    
  }
  
  
  
  void setEdge( const string & a_name, const string & b_name,int in_weight )//建立一个从a指向b的边
  {
    
    edge tmp_edge;
    vertex *A;
    vertex *B;
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
       	
	if(  (*itr).name == a_name )
	  A = &(*itr);
	if( (*itr).name == b_name )
	  B = &(*itr);
	
      }
    
    for( itrEdge = A->edgeList.begin(); itrEdge != A->edgeList.end(); itrEdge++)
      {
	if( (*itrEdge).v->name == b_name )
	  {
	    deleteEdge(a_name, b_name);
	    break;
	  }
      }//如果图中已经存在这条边了，则将原来的边覆盖掉

    tmp_edge.v = B;
    tmp_edge.weight = in_weight;
    tmp_edge.direction = 1;   
    A->edgeList.push_back( tmp_edge );
    
    tmp_edge.v = A;
    tmp_edge.direction = 0;
    B->edgeList.push_back( tmp_edge );
    
  }
  
  void deleteEdge( const string & a_name, const string & b_name )
  {
    
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
	if( itr->name == a_name )
	  for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)
	    {
	      if( (*itrEdge).v->name == b_name)
		{
		  (*itr).edgeList.erase( itrEdge );
		  break;
		}
	    } //删掉a中存储的关于b的边
	
	if( itr->name == b_name )
	  for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)
	    {
	      if( (*itrEdge).v->name == a_name)
		{
		  (*itr).edgeList.erase( itrEdge );
		  break;
		}
	    } //删掉b中存储的关于a的边	  
      }   
    
  }


  
  //void list(){}
   
 void listVertex()
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	cout << (*itr).name << " : "<< (*itr).data << endl;
      }

  }
  
  void listEdge()
  {
    string output;    //将数据调整为想要的输出格式
    string revise_output;
    
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++ )
	  {
      	     if( (*itrEdge).direction )//只输出从当前结点指出的边，防止重复输出.无向图当成是对应两倍边长数的有向图.
	     {
		output = "(";
		output += (*itr).name;
		output +=", ";
		output += (*itrEdge).v->name;
		output +=", ";
		output += to_string( (*itrEdge).weight );
		output +=")";
	    
		cout<< output << " ";
		 }
	  }
					      
      }
  }
  
  
};






/**
 *邻接矩阵法实现GRAPH
 */		 
template<typename Object>
class graph_matrix 
{
private:
  
  class vertex{
  public:
    Object data;
    string name;    
  };
  class edge{
  public:
    int weight;
    int direction;

    edge& operator=( edge &rhs)
    {
      weight = rhs.weight;
      direction = rhs.direction;
      return *this;
    }
  };
  
  list<vertex> vertexList;
  typename list<vertex>::iterator itr;

  edge edge_matrix[21][21];//最大容量是20个顶点
  
	    
public:
  /**
   *初始化二维矩阵
   */
  graph_matrix(){
    for(int i=0; i < 21; i++)
      {
	for(int j=0; j < 21; j++)
	  {
	    edge_matrix[i][j].weight = 0;
	    edge_matrix[i][j].direction = -1;
	  }
      }
    
  }

  void insertVertex( const Object &in_data, const string &in_name )
  {
    vertex temp;
    temp.name = in_name;
    temp.data = in_data;
    vertexList.push_back( temp );
  }
  
  void deleteVertex( const string &name )
  {
    int flag = 0;
    for( itr = vertexList.begin(); itr != vertexList.end(); flag++,itr++)
      {
	if((*itr).name == name)
	  {
	    vertexList.erase( itr );
	    break;
	  }
      }
    
    int i,j;
    
    for( i=0; i <= vertexList.size() ; i++)
      {
	for( j=0; j<= vertexList.size(); j++)
	  {
	    if( j >= flag)
	     edge_matrix[i][j] = edge_matrix[i][j+1];	 
	  }
      }

    
    for( i=0; i <= vertexList.size() ; i++)
      {
	for( j=0; j<= vertexList.size(); j++)
	  {
	    if( i >= flag)
	     edge_matrix[i][j] = edge_matrix[i+1][j];	 
	  }
      }
  }
  
  void setEdge( const string &a_name, const string &b_name, int in_weight )
  {
    int i=0,j=0,k=0;
    int flag_1=0, flag_2=0;
    
    for( itr = vertexList.begin(); itr != vertexList.end(); k++,itr++)
      {
	if((*itr).name == a_name)
	  i = k, flag_1 = 1;
	if((*itr).name == b_name )
	  j = k, flag_2 = 1;	
      }
    
    if( flag_1 && flag_2 )//在顶点中找到输入的两个顶点才操作。否则直接返回
      {
	edge_matrix[i][j].weight = in_weight;
	edge_matrix[i][j].direction = 1;
	
	edge_matrix[j][i].weight = in_weight;
	edge_matrix[j][i].direction = 0;
      }
    return;
  }
  
  void deleteEdge( const string & a_name, const string & b_name )
  {

    int i=0,j=0,k=0;
    int flag_1=0, flag_2=0;
    
    for( itr = vertexList.begin(); itr != vertexList.end(); k++,itr++)
      {
	if((*itr).name == a_name)
	  i = k, flag_1 = 1;
	if((*itr).name == b_name )
	  j = k, flag_2 = 1;	
      }
    
    if( flag_1 && flag_2 )//在顶点中找到输入的两个顶点才操作。否则直接返回
      {
	edge_matrix[i][j].weight = 0;
	edge_matrix[i][j].direction = -1;
	
	edge_matrix[j][i].weight = 0;
	edge_matrix[j][i].direction = -1;
      }
    return;
  }

  
  void listVertex()
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
	
	  cout << (*itr).name << " : "<< (*itr).data << endl;
      }
  }
  
  void listEdge()
  {
    string output;
    typename list<vertex>::iterator itr_1;
    typename list<vertex>::iterator itr_2;
    int i,j; 
    
    
    for( i=0,itr_1 = vertexList.begin(); itr_1 != vertexList.end(); i++,itr_1++ )
      {
	for( j=0,itr_2 = vertexList.begin(); itr_2 !=vertexList.end(); j++,itr_2++ )
	  if( edge_matrix[i][j].direction == 1 )
	    {
		output = "(";
		output += (*itr_1).name;
		output +=", ";
		output += (*itr_2).name;
		output +=", ";
		output += to_string( edge_matrix[i][j].weight );
		output +=")";
	    
		cout<< output << " ";


	    }
      }
  }



};
